import numpy as np
import warnings
import matplotlib.pyplot as plt

class PolygonClipper:
    
    def __init__(self, warn_if_empty=True):
        self.warn_if_empty = warn_if_empty  # 控制是否在没有交集时发出警告
    
    def is_inside(self, p1, p2, q):
        # 检查点 q 是否在裁剪边 p1 -> p2 的内部
        R = (p2[0] - p1[0]) * (q[1] - p1[1]) - (p2[1] - p1[1]) * (q[0] - p1[0])
        return R <= 0  # 如果 R <= 0，则 q 在边的内部或边上
    
    def compute_intersection(self, p1, p2, p3, p4):
        # 计算两条线段 p1 -> p2 和 p3 -> p4 的交点
        if p2[0] - p1[0] == 0:  # 第一条线段垂直
            x = p1[0]
            m2 = (p4[1] - p3[1]) / (p4[0] - p3[0])
            b2 = p3[1] - m2 * p3[0]
            y = m2 * x + b2
        elif p4[0] - p3[0] == 0:  # 第二条线段垂直
            x = p3[0]
            m1 = (p2[1] - p1[1]) / (p2[0] - p1[0])
            b1 = p1[1] - m1 * p1[0]
            y = m1 * x + b1
        else:  # 两条线段都不是垂直的
            m1 = (p2[1] - p1[1]) / (p2[0] - p1[0])
            b1 = p1[1] - m1 * p1[0]
            m2 = (p4[1] - p3[1]) / (p4[0] - p3[0])
            b2 = p3[1] - m2 * p3[0]
            x = (b2 - b1) / (m1 - m2)  # 计算交点的 x 坐标
            y = m1 * x + b1  # 基于直线方程计算交点的 y 坐标
        return (x, y)  # 返回交点坐标
    
    def clip(self, subject_polygon, clipping_polygon):
        final_polygon = subject_polygon.copy()  # 初始化当前多边形为待裁剪多边形
        
        # 对每条裁剪边进行循环
        for i in range(len(clipping_polygon)):
            next_polygon = final_polygon.copy()  # 保存当前多边形以供下一次迭代
            final_polygon = []  # 重置最终多边形

            # 获取裁剪边的起点和终点
            c_edge_start = clipping_polygon[i - 1]
            c_edge_end = clipping_polygon[i]
            
            # 对当前多边形的每条边进行循环
            for j in range(len(next_polygon)):
                s_edge_start = next_polygon[j - 1]  # 当前边的起点
                s_edge_end = next_polygon[j]  # 当前边的终点

                inside_end = self.is_inside(c_edge_start, c_edge_end, s_edge_end)  # 判断终点是否在裁剪边内
                inside_start = self.is_inside(c_edge_start, c_edge_end, s_edge_start)  # 判断起点是否在裁剪边内

                # 如果终点在裁剪边内
                if inside_end:
                    if not inside_start:  # 起点在外部:
                        # 计算交点并添加
                        intersection = self.compute_intersection(s_edge_start, s_edge_end, c_edge_start, c_edge_end)
                        if intersection not in final_polygon:  # 确保不重复添加交点
                            final_polygon.append(intersection)  # 添加交点
                    final_polygon.append(tuple(s_edge_end))  # 添加终点到最终多边形
            
                # 如果起点在裁剪边内
                elif inside_start:
                    # 计算交点并添加
                    intersection = self.compute_intersection(s_edge_start, s_edge_end, c_edge_start, c_edge_end)
                    if intersection not in final_polygon:  # 确保不重复添加交点
                        final_polygon.append(intersection)  # 添加交点

        return np.asarray(final_polygon)  # 返回最终裁剪后的多边形
    
    def __call__(self, A, B):
        clipped_polygon = self.clip(A, B)  # 执行裁剪
        
        if len(clipped_polygon) == 0 and self.warn_if_empty:
            warnings.warn("No intersections found. Are you sure your polygon coordinates are in clockwise order?")
        
        return clipped_polygon

def plot_polygon(polygon, color, label):
    """ 绘制多边形 """
    plt.fill(*zip(*polygon), color=color, alpha=0.5, label=label)

if __name__ == '__main__':
    clip = PolygonClipper()

    # 定义一个凹多边形和裁剪窗口
    subject_polygon = np.array([(0,3), (0.5,0.5), (3,0), (0.5,-0.5), (0,-3), (-0.5,-0.5), (-3,0), (-0.5,0.5)])
    clipping_polygon = np.array([(-2,-2), (-2,2), (2,2), (2,-2)])
    
    # 进行裁剪
    clipped_polygon = clip(subject_polygon, clipping_polygon)

    # 绘制原始多边形和裁剪多边形
    plt.figure(figsize=(8, 8))
    plot_polygon(subject_polygon, 'blue', 'Subject Polygon')  # 绘制待裁剪多边形
    plot_polygon(clipping_polygon, 'red', 'Clipping Polygon')  # 绘制裁剪多边形

    # 检查并绘制裁剪后的多边形
    if clipped_polygon.size > 0:
        plot_polygon(clipped_polygon, 'green', 'Clipped Polygon')  # 绘制裁剪后的多边形
    
    plt.xlim(-4, 4)  # 设置 x 轴范围
    plt.ylim(-4, 4)  # 设置 y 轴范围
    plt.axhline(0, color='black', linewidth=0.5, ls='--')  # 绘制 x 轴
    plt.axvline(0, color='black', linewidth=0.5, ls='--')  # 绘制 y 轴
    plt.grid()  # 显示网格
    plt.gca().set_aspect('equal', adjustable='box')  # 设置坐标轴比例
    plt.title('Polygon Clipping')  # 设置标题
    plt.legend()  # 显示图例
    plt.show()  # 显示图形
